package com.lw.leetcode.back.b;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 剑指 Offer 38. 字符串的排列
 * 面试题 08.08. 有重复字符串的排列组合
 *
 * @Author liw
 * @Date 2021/6/22 9:37
 * @Version 1.0
 */
public class Permutation {

    public static void main(String[] args) {
        Permutation test = new Permutation();
        String[] abcs = test.permutation("AAAABB");
        System.out.println(Arrays.toString(abcs));
    }

    private int length;
    List<String> list = new ArrayList<>();

    public String[] permutation(String s) {
        chars = s.toCharArray();
        length = chars.length;
        StringBuilder sb = new StringBuilder(length);
        boolean[] flag = new boolean[length];
        find(sb, flag, 0);
        return list.stream().distinct().toArray(String[]::new);
    }

    private void find(StringBuilder sb, boolean[] flag, int n) {
        if (n == length) {
            list.add(sb.toString());
            return;
        }
        for (int i = 0; i < length; i++) {
            if (flag[i]) {
                continue;
            }
            flag[i] = true;
            sb.append(chars[i]);
            find(sb, flag, n + 1);
            flag[i] = false;
            sb.deleteCharAt(n);
        }
    }

    private char[] chars;

    public String[] permutation2(String str) {
        this.list = new ArrayList<>();
        this.chars = str.toCharArray();
        this.length = chars.length;
        Arrays.sort(chars);
        char[] arr = new char[length];
        find(0, arr);
        String[] strs = new String[list.size()];
        int i = 0;
        for (String s : list) {
            strs[i++] = s;
        }
        return strs;
    }

    private void find(int index, char[] arr) {
        if (index == length) {
            list.add(new String(arr));
            return;
        }
        int last = '*';
        for (int i = 0; i < length; i++) {
            char c = chars[i];
            if (c == '*' || c == last) {
                continue;
            }
            last = c;
            arr[index] = c;
            chars[i] = '*';
            find(index + 1, arr);
            chars[i] = c;
        }
    }


}
